/*
 * @Author: liusheng
 * @Date: 2022-06-07 09:59:20
 * @LastEditors: liusheng
 * @LastEditTime: 2022-06-07 10:05:27
 * @Description: 剑指 Offer II 074. 合并区间
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 */

#include "header.h"
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end());
        vector<int> interval = intervals[0];
        vector<vector<int>> merged;
        for (int i = 1; i < intervals.size(); ++i)
        {
            //overlapping
            if (interval[1] >= intervals[i][0])
            {
                interval[1] = max(interval[1],intervals[i][1]);
            }
            else
            {
                merged.push_back(interval);
                interval = intervals[i];
            }
        }

        //push the last one
        merged.push_back(interval);
        return merged;
    }
};